package find.prj.lib;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Graph {
	
	protected ArrayList<GraphNode> Nodes;
	
	public Graph() {
		this.Nodes = new ArrayList<GraphNode>();
	}
	
	public ArrayList<GraphNode> getNodes() { return this.Nodes; }
	
	public void Clear() { this.Nodes.clear(); }
	
	// readNodeNames = true if connectivity matrix file has node names in 1st line
	public void LoadConnectivityMatrixFromFile(String fileName, boolean readNodeNames) {
		this.Clear();
		BufferedReader reader = null;
		try {
			final int BUFFER_SIZE = 10000;
			reader = new BufferedReader(new FileReader(fileName));
			reader.mark(BUFFER_SIZE);
		    String readString;
		    String[] nodeNames, readStringElements;
		    int nodeCount;
		    readString = reader.readLine().trim();	//reading 1st line to read node names (if readNodeNames) or check node count (if !readNodeNames)
		    if (readNodeNames) {
		    	nodeNames = readString.split(" ");
		    	nodeCount = nodeNames.length;
		    }
		    else {
		    	nodeCount = readString.split(" ").length;
		    	nodeNames = new String[nodeCount];
		    	for (int i=0; i < nodeCount; i++)
		    		nodeNames[i] = "N-"+(i+1); 
		    	reader.reset();
		    }
		    for (int i=0; i < nodeNames.length; i++)
		    	this.Nodes.add(new GraphNode(nodeNames[i]));

		    for (int i=0; i < nodeNames.length; i++) {
		    	readStringElements = reader.readLine().split(" ");
		    	for (int k=0; k < readStringElements.length; k++) {
		    		int kInt = Integer.valueOf(readStringElements[k]);
		    		if (kInt != 0) {
		    			GraphLink newLink = new GraphLink(this.Nodes.get(k), kInt); 
		    			this.Nodes.get(i).Links.add(newLink);
		    		}
		    	}
		    }
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			if (reader != null)
				try {
					reader.close();
				} catch (IOException e) {
					e.printStackTrace();
				}
		}
		
	}
	
	public int[][] getConnectivityMatrix() {
		int nodeCount = this.Nodes.size();
		int[][] matrix = new int[nodeCount][nodeCount];
		for (int i=0; i < nodeCount; i++)
			for (int k=0; k < nodeCount; k++)
				matrix[i][k]=0;
		for (int i=0; i < nodeCount; i++) {
			GraphNode node = this.Nodes.get(i);
			for (GraphLink link : node.Links)
				matrix[i][this.Nodes.indexOf(link.getToNode())]=link.getDistance(); 
		}
		return matrix;
	}
	
	public String getConnectivityMatrixtoString(boolean writeNodeNames) {
		StringBuilder result = new StringBuilder();
		int[][] matrix = this.getConnectivityMatrix();
		if (writeNodeNames) {
			for (GraphNode node : this.Nodes)
				result.append(node.getName() + " ");
			result.replace(result.length()-1, result.length(), "\n");
		}
		for (int i=0; i < matrix.length; i++) {
			for (int k=0; k < matrix.length; k++)
				result.append(matrix[i][k]+" ");
			result.replace(result.length()-1, result.length(), "\n");
		}
		return result.toString().trim();
	}
	
	public void SaveConnectivityMatrixToFile(String fileName, boolean writeNodeNames) {
		BufferedWriter writer = null;
		String matrix = this.getConnectivityMatrixtoString(writeNodeNames);
		try	{
			writer = new BufferedWriter( new FileWriter(fileName));
			writer.write(matrix);
		}
		catch ( IOException exception) {
		}
		finally	{
			try	{
				if ( writer != null)
					writer.close( );
			}
			catch ( IOException exception) {
			}
		}

	}
	
	public String getConnectivityMatrixToCSVToString(boolean writeNodeNames) {
		StringBuilder result = new StringBuilder();
		int[][] matrix = this.getConnectivityMatrix();
		if (writeNodeNames) {
			for (GraphNode node : this.Nodes)
				result.append("\"" + node.getName() + "\";");
			result.replace(result.length()-1, result.length(), "\n");
		}
		for (int i=0; i < matrix.length; i++) {
			for (int k=0; k < matrix.length; k++)
				result.append(matrix[i][k]+";");
			result.replace(result.length()-1, result.length(), "\n");
		}
		return result.toString().trim();
	}
	
	public void SaveConnectivityMatrixToCSV(String fileName, boolean writeNodeNames) {
		BufferedWriter writer = null;
		String matrix = this.getConnectivityMatrixToCSVToString(writeNodeNames);
		try	{
			writer = new BufferedWriter( new FileWriter(fileName));
			writer.write(matrix);
		}
		catch ( IOException exception) {
		}
		finally	{
			try	{
				if ( writer != null)
					writer.close( );
			}
			catch ( IOException exception) {
			}
		}
	}
	
	public ArrayList<GraphRoute> getAllRoutes(int fromNodeIndex, int toNodeIndex) {
		ArrayList<GraphRoute> routes = new ArrayList<GraphRoute>();
		routes.add(new GraphRoute());
		getAllRoutesHelper(Nodes.get(fromNodeIndex), Nodes.get(toNodeIndex), routes, 0);
		return routes;
	}
	
	private void getAllRoutesHelper(GraphNode fromNode, GraphNode toNode, ArrayList<GraphRoute> routes, int routeIndex) {
		if (fromNode == toNode) {
			GraphRoute newRoute = new GraphRoute(routes.get(routeIndex));
			newRoute.Nodes.add(fromNode);
			routes.add(newRoute);
			routes.remove(routes.get(routeIndex));
			return;
		}
		GraphRoute currentRoute = routes.get(routeIndex);
		for (GraphLink link : fromNode.Links) {
			if (currentRoute.Nodes.contains(link.ToNode))
				continue;
			GraphRoute newRoute = new GraphRoute(currentRoute);
			newRoute.Nodes.add(fromNode);
			newRoute.Length += link.Distance;
			routes.add(newRoute);
			int newIndex = routes.size()-1;
			getAllRoutesHelper(link.ToNode, toNode, routes, newIndex);
		}
		routes.remove(routes.get(routeIndex));
	}
	
	public GraphRoute getShortestRouteByExhaustiveSearch(int fromNodeIndex, int toNodeIndex) {
		ArrayList<GraphRoute> routes = this.getAllRoutes(fromNodeIndex, toNodeIndex);
		GraphRoute minRoute = routes.get(0);
		int minDistance = minRoute.Length; 
		for (GraphRoute route : routes) {
			if (route.Length < minDistance) {
				minRoute = route;
				minDistance = route.Length;
			}
		}
		return minRoute;
	}
	
	public GraphRoute getShortestRouteByDijkstra (int fromNodeIndex, int toNodeIndex) {
		GraphNode fromNode = Nodes.get(fromNodeIndex);
		GraphNode toNode = Nodes.get(toNodeIndex);
		HashMap<GraphNode, Integer> distTo = new HashMap<GraphNode, Integer>();
		HashMap<GraphNode, GraphNode> prevNodeInRoute = new HashMap<GraphNode, GraphNode>();
		HashMap<GraphNode, Boolean> isUsed = new HashMap<GraphNode, Boolean>();

		for (GraphNode node: this.Nodes) {
			distTo.put(node, Integer.MAX_VALUE/2);
			prevNodeInRoute.put(node,null);
			isUsed.put(node, false);
		}
		distTo.put(fromNode, 0);

		GraphNode viewingNode = fromNode;
		for (int i=0; i < this.Nodes.size(); i++) {
			isUsed.put(viewingNode, true);
			if (distTo.get(viewingNode) >= Integer.MAX_VALUE/2)
				continue;
			if (! viewingNode.Links.isEmpty())
				for (GraphLink link: viewingNode.Links) {
					int checkDist = distTo.get(viewingNode) + link.Distance; 
					if (checkDist < distTo.get(link.ToNode)) {
						distTo.put(link.ToNode, checkDist);
						prevNodeInRoute.put(link.ToNode, viewingNode);
					}
				}
			viewingNode = leastDistUnusedNode(distTo, isUsed);
		}
					
		GraphRoute reverseRoute = new GraphRoute();
		GraphRoute route = new GraphRoute();
		GraphNode prevNode = toNode;
		reverseRoute.Nodes.add(toNode);
		while (prevNode != fromNode) {
			reverseRoute.Nodes.add(prevNodeInRoute.get(prevNode));
			prevNode = prevNodeInRoute.get(prevNode);
		}
		for (int i=reverseRoute.Nodes.size()-1 ; i >=0 ; i--)
			route.Nodes.add(reverseRoute.Nodes.get(i));
		route.Length = distTo.get(toNode);
		return route;
	}
	
	private GraphNode leastDistUnusedNode(HashMap<GraphNode, Integer> distTo, HashMap<GraphNode, Boolean> isUsed) {
		Integer minDist = Integer.MAX_VALUE;
		GraphNode resultNode = Nodes.get(0);
		for (Map.Entry<GraphNode, Integer> distEntry : distTo.entrySet()) {
			if ( (distEntry.getValue() < minDist) && !(isUsed.get(distEntry.getKey())) ) {
				minDist = distEntry.getValue();
				resultNode = distEntry.getKey();
			}
		}
		return resultNode;
	}
	
}
